package com.dong.binaryTree;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 二叉树的层序遍历
 * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
 */

class TreeNode3 {
    int val;//存放值
    TreeNode3 left;//指向左节点
    TreeNode3 right;//指向右节点
    TreeNode3(){};
    TreeNode3(int val){
        this.val = val;
    }

    public TreeNode3(int val, TreeNode3 left, TreeNode3 right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class LevelOrder {

    public List<List<Integer>> resList = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder(TreeNode3 root) {
        checkFun02(root);
        return resList;
    }

    public void checkFun02(TreeNode3 node) {
        if (node == null){
            return;
        }
        Queue<TreeNode3> que = new LinkedList<>();
        que.offer(node);
        while (!que.isEmpty()){
            List<Integer> itemList = new ArrayList<>();
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            int len = que.size();
            while (len>0){
                TreeNode3 tmpNode = que.poll();
                itemList.add(tmpNode.val);
                if (tmpNode.left !=null){
                    que.offer(tmpNode.left);
                }
                if (tmpNode.right != null){
                    que.offer(tmpNode.right);
                }
                len--;

            }
            resList.add(itemList);
        }

    }
}
